package com.example.myapplication.Algorithm.Fiblist;

public class FibList {
    public static void main(String[] args){
        ///解斐波拉切数列
        System.out.println(calculate(10));
        System.out.println(calculate2(10));
        System.out.println(iterate(10));
    }

    ///暴力解法 O(2^n)
    public static int calculate(int num){
        if(num==0){
            return 0;
        }

        if(num==1){
            return 1;
        }
        return calculate(num-1)+calculate(num-2);
    }
    ///去重O(N) + O(N)
    public static int calculate2(int num){
        int[] arr = new int [num+1];//10 = 0+10
        if(num==0){
            return 0;
        }

        if(num==1){
            return 1;
        }
        return recurse(arr,num-1)+recurse(arr,num-2);
    }
    //单独的存储递归
    private static int recurse(int[] arr,int num){
        if(num==0){
            return 0;
        }
        if(num==1){
            return 1;
        }
        if(arr[num]!=0){
            return arr[num];
        }
        arr[num] =  recurse(arr,num-1)+recurse(arr,num-2);
        return arr[num];
    }

    //双指针迭代 O(N)
    private static int iterate(int num){
        ///双指针:前后指针，左右指针，快慢指针
        ///（一直向右移，01 12 23）
        if(num==0){
            return 0;
        }
        if(num==1){
            return 1;
        }
        int low = 0;
        int high = 1;
        for(int i=2;i<=num;i++){
            int sum = low + high;
            low = high;
            high = sum;
        }
        return high;
    }
}
